Digital commerce requires digital methods for ensuring that a document does not come from an impostor and that the document has not been altered during delivery. Bruce Schneier has given a comprehensive introduction to the art and science of keeping digital messages secure in his book "Applied Cryptography, Second Edition" published by John Wiley & Sons, Inc., New York (1996).
Some of the schemes that the cryptography community has devised for digital signatures and authentications involve the exponentiation of long integers modulo a public integer that is also hundreds of digits long. The security of these schemes depends on the infeasibility of computing discrete logarithms to learn the secret exponents.
Discrete-log based systems have been widely studied and used in recent decades. Examples include Diffie-Hellman key exchange, ElGamal encryption, ElGamal and DSS signatures, and Schnorr's schemes for authentication and signatures. These schemes require generation of pairs of the form (k, g.sup.k modulo p) where k is randomly distributed modulo on the order of g, p is preferably a positive prime number that is hundreds of digits long, and g&lt;p is another positive integer that may be only a single-digit number. In modular arithmetic, the value of any non-negative integer Q modulo p is the remainder of the division Q/p, and the possible values are the integers in the range [0, p-1].
Usually, g is a generator of p, which means that there exists some integer k such that y=g.sup.k modulo p for each integer y in the set [1,p-1]. Because p is preferably prime, g cannot divide it evenly, so 0 and p are not in the set. This set is called Z*.sub.p, and its members form a group with respect to multiplication modulo p. When g is not a generator modulo p, the possible values of g.sup.k modulo p still form a group with respect to multiplication modulo p. That is, the product of any two values g.sup.k and g.sup.k' modulo p is equal to g.sup.k+k' modulo p, which is also a member of the group. The set of distinct integers forming this group are 1, g, g.sup.2, . . . , g.sup.ord(g)-1 where ord(g) is shorthand for the order of g in p. Thus k is in the set [0, ord(g)-1], and g.sup.k is a member of Z.sub.ord(g). The set [0, ord(g)-1] is also referred to as Z.sub.ord(g), and its members form a group with respect to addition modulo ord(g).
A. Diffie-Hellman Key Agreement Protocol
Two parties can use this algorithm to securely establish a secret key by exchanging public keys on an insecure connection. Each party also has a private key, and both of them are able to calculate the same secret key from their own private key and the other party's public key. The parties can then use secret-key cryptographic techniques to exchange further messages securely.
The two Diffie-Hellmann parameters p and g are public. Any two parties Alice and Bob who want to establish a secret key each choose private keys k.sub.a and k.sub.b, respectively. Alice computes her public key g.sup.k.sbsp.a modulo p and sends it to Bob, and he computes his public key g.sup.k.sbsp.b modulo p and sends it to her. A third party Eve who copies the two public keys cannot calculate either of the private keys by known methods unless p-1 has only small prime factors. Therefore values of p where p-1 has at least one large prime factor are often used in cryptography. Alice computes the common session key as (g.sup.k.sbsp.b modulo p).sup.k.sbsp.a modulo p and Bob computes it as (g.sup.k.sbsp.a modulo p).sup.k.sbsp.b modulo p. A useful result of number theory is that (g.sup.k.sbsp.b modulo p).sup.k.sbsp.a modulo p is equal to g.sup.k.sbsp.b.sup.k.sbsp.a.sup.modulo f(p) modulo p, where f(p) is the Euler totient function. The modular arithmetic in the exponent does not depend on the order of k.sub.a and k.sub.b, so Alice and Bob compute the same result.
B. ElGamal Encryption
ElGamal encryption also relies on the difficulty of calculating discrete logarithms for its security. Alice can use this algorithm to encrypt a message M in such a way that only Bob can read it. The message M is restricted to be less than p, and all the calculations that follow are to be performed modulo p. Of course, a longer message can be sent in sufficiently many short installments. First, Alice chooses a random number pair k and g.sup.k modulo p as above, but they are not really the key pair. Bob chooses his private key x and calculates his public key y=g.sup.x modulo p. Alice uses Bob's public key y to encrypt M by computing My.sup.k modulo p and sends e(M, k)=(g.sup.k, My.sup.k) to Bob. Bob uses the first part and his secret key x to calculate (g.sup.k).sup.x =(g.sup.x).sup.k =y.sup.k. Then he divides this result into the second part of the signature that he received from Alice to recover the message M.
C. ElGamal Signatures
To sign a message M, Alice proves to Bob that she used her private key x while only revealing her public key y=g.sup.x modulo p. Alice also chooses a second pair k and g.sup.k modulo p where k must be relatively prime to p-1. This means that the two numbers k and p-1 share no common divisor other than 1. The signature s(M, k) that Alice presents to Bob comprises the two quantities r and s where r=g.sup.k modulo p and M=(xr+ks) modulo (p-1). Alice can solve for s because k.sup.-1 modulo (p-1) exists when k and p-1 are relatively prime. At this point Alice and Bob know p, g, y, r and s. Of course, Bob also knows the message M that Alice has signed. To verify the signature, Bob checks whether r.sup.s y.sup.r =g.sup.M. This turns out to be the case because f(p) is equal to p-1 when p is prime so r.sup.s y.sup.r modulo p is equal to g.sup.(xr+ks)modulo(p-1) modulo p.
D. DSS Signatures
In DSS signatures, q is a large prime divisor of p-1, and g.sup.q =1 modulo p. Alice chooses a secret key x and publishes y=g.sup.x modulo p. To form a signature s(M, k)=(r, s) of a message M, Alice chooses k and computes r=(g.sup.k modulo p) modulo q and s=(M+xr)k.sup.-1 modulo q. Bob calculates ((g.sup.M y.sup.r).sup.s-1 modulo p) modulo q. Using the definition of Alice's public key y allows the term y.sup.r modulo p to be simplified to (g.sup.x).sup.r modulo p=g.sup.xr modulo f(p) =g.sup.xr modulo q because p is prime, f(p)=p-1, xr mod p-1 is xr mod q plus some integer times q, and g.sup.q =1. Also (g.sup.M).sup.s-1 modulo p=g.sup.Ms-1 modulo q modulo p because Ms.sup.-1 modulo p-1 is Ms.sup.-1 modulo q plus some integer times q and g.sup.q =1. Thus, if Alice used her private key x and her secret k in evaluating s, Bob should find that ((g.sup.M y.sup.r).sup.s-1 modulo p) modulo q=(g.sup.(M+xr)s-1 modulo q modulo p) modulo q=(g.sup.k modulo q modulo p) modulo q=(g.sup.k modulo p) modulo q=r.
E. Schnorr Authentication
Authentication schemes allow Alice to prove to Bob that she knows a secret without Bob knowing or learning the secret himself. For example, suppose Bob is a server and the secret is Alice's password. The server does not need to know Alice's password; it only needs to verify that Alice knows it. The security design of the server is much more robust if the passwords are not kept, even in encrypted form.
In Schnorr's authentication scheme, q is a large prime divisor of p-1 and g.sup.q =1 modulo p. Alice generates a private key s that is less than q and calculates her public key v=a.sup.-S modulo p. When Alice wants to prove that she knows her secret s to Bob, she generates a random k .epsilon. Z*.sub.q and computes x=g.sup.k. Alice sends x to Bob, who then picks a random number r between 0 and 2.sup.t -1 and sends it back to Alice. At this point Alice and Bob both know p, g, q, v, x, and r, but only Alice knows k, and only the real Alice knows s. Alice sends y=(k+sr) modulo q to Bob. Bob computes g.sup.y v.sup.r =g.sup.(k+sr) modulo q (g.sup.-s modulo p).sup.r. The product of the exponents is calculated modulo f(p)=p-1, so Bob has g.sup.(k+sr) modulo q g.sup.-Sr modulo p-1. Because q is a divisor of p-1, -sr modulo p-1 is -sr mod q plus some integer times q, but g.sup.q =1, so Bob is left with g.sup.k, which he can verify is x. An impostor trying to spoof Bob by guessing some s' would succeed if (s'-s)r modulo q=0.
F. Schnorr Signatures
In Schnorr's signature scheme, q is a large prime divisor of p-1 and g.sup.q =1 modulo p. Alice generates a private key s that is less than q and calculates her public key v=a.sup.-s modulo p. Thus p, q, g, s and v are defined in the same way as they are in Schnorr authentication. Alice forms a signature s(M, k)=(r, y) where r=h(g.sup.k, M) is a hash function giving a value in the range between 0 and 2.sup.t -1 and y=(k+sr) modulo q. At this point Alice and Bob both know the message M and p, g, q, v, y and r, but only Alice knows k, and only the real Alice knows s. Bob does not know g.sup.k. However, Bob computes g.sup.y v.sup.r =g.sup.(k+sr) modulo q (g.sup.-s modulo p).sup.r. The product of the exponents is calculated modulo f(p)=p-1, so Bob has g.sup.(k+sr) modulo q g.sup.-sr modulo p-1. Because q is a divisor of p-1, -sr modulo p-1 is -sr mod q plus some integer times q, but g.sup.q =1, so Bob is left with g.sup.k if the signature is genuine. He then performs the hash himself to verify that h(g.sup.k, M)=r. As with Schnorr authentication, only Alice knows k and only the real Alice knows s. An imposter trying to forge Alice's signature by guessing that her private key is s' would succeed if (s'-s)r modulo q=0.
G. 2.sup.m th Root Identification Scheme (Shoup Authentication)
Victor Shoup first described this authentication protocol in a paper "On the Security of a Practical Identification Scheme," in Advances in Cryptology: EUROCRYPT'96, Ueli Maurer, editor, volume 1070 of Lecture Notes in Computer Science, pages 344-353, Springer-Verlag, Berlin (1996). The modulus is a product of two randomly selected primes p and q of equal length, and both of them are equal to 3 modulo 4. The public exponent is e=2.sup.m. Alice chooses positive integer a .epsilon. Z*.sub.pq as her private key and computes b=.sup.e a modulo pq for her public key. When Alice wants to prove that she knows her secret key a to Bob, she chooses positive integer k .epsilon. Z*.sub.pq at random, computes x=k.sup.e modulo pq, and sends x to Bob. Bob chooses r at random in [0, e-1] and sends r to Alice. Alice computes y=ka.sup.r modulo pq and sends y to Bob. At this point Alice and Bob know pq and b, x, r and y. Alice knows pq and, if she is the real Alice, she also knows a. Bob computes y.sup.e =(ka.sup.r modulo pq).sup.e modulo pq=k.sup.e a.sup.re modulo (p-1)(q-1) modulo pq using Euler's totient (p-1)(q-1) for a product of primes p and q. The order of exponentiation can be reversed, so Bob should verify that y.sup.e =k.sup.e (a.sup.e modulo pq).sup.r modulo pq=xb.sup.r modulo pq. An impostor trying to spoof Bob would be faced with the problem of determining Alice's private key by taking the e.sup.th root of b modulo pq. This is hard if factoring pq is hard. Shoup showed that the scheme is even secure against active attacks, if factoring pq is hard. In an active attack, the impostor is free to interact with Bob repeatedly and can depart from the protocol.
State-of-the-art personal computers can typically calculate a public-key pair of the form (k, g.sup.k modulo p) or (k, .sup.e k modulo p) in less than a second. This is tolerable for transactions that are done infrequently, which is likely to be the case in truly "personal" computer applications. However, the personal computer has become a commodity, and high-end PCs are also being used successfully as servers by small Internet service providers. In such applications, the computational load is compounded by the average number of users and will become a bottleneck as secure electronic commerce expands. Therefore, it is the object of the present invention to provide a more efficient method of calculating random key pairs for use with public-key algorithms that are based on the infeasibility of calculating discrete logarithms or factoring a number constructed by multiplying two large primes.